//
// Created by user on 2022/3/15.
//

#include <iostream>
#include <unordered_set>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    };

ListNode *detectCycle(ListNode *head) {
    unordered_set<ListNode*> set;
    while (head!= nullptr){
        if(set.count(head)){
            return head;
        }
        set.insert(head);
        head = head->next;
    }
    return nullptr;
}

ListNode *detectCycle1(ListNode *head) {

    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode *p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;
        }
    }
    return nullptr;
}